# 剑指Offer题解 - Day66
# 剑指 Offer 60. n 个骰子的点数
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
示例 1:
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
2
限制：
1 <= n <= 11
分析：
首先考虑使用暴力法。先根据题目描述总结以下结论：
- 每个骰子摇到1~6的概率相等，均等于
1/6； - 一个骰子的点数之和有6种情况，两个骰子的点数之和有36种情况，n个骰子有
6^n种情况。 - n个骰子的点数之和范围是
[n, 6n]，点数出现的可能性个数是 6n - n + 1 = 5n + 1。
如果使用暴力法，需要统计每个点数和的出现次数，然后除以点数之和的总数6^n 。由题目可知，1 <= n <= 11 ，因此暴力法是无法接受的。
# 动态规划
此题可以通过动态规划求解。因此我们需要找出dp方程。核心的问题在于，假设n - 1个骰子的解是f(n - 1)，如何递推出n个骰子的解f(n) 。
- 假设n个骰子点数之和为x的解为
f(n, x)； - 如果当前添加的骰子点数是1，那么n - 1个骰子的点数之和就是x - 1。以此类推直到当前添加的骰子点数是6，那么n - 1个骰子的点数之和就是x - 6。由此可得：
f(n - 1, x - i)的累加和除以6就是f(n, x)的解。其中，i的取值范围是1~6。 - 而f(1)的解是已知的，因此可以通过上述方程求出
f(n)。
由此，我们得出了逆向求解方程。此时衍生出一个新的问题，x可能会越界。如果x小于6的话，此时的计算是毫无意义的。
那么可以换一种思维，先求出f(n - 1)中各点数和的概率。而f(n - 1, x)仅与f(n, x + i)相关，其中i的取值范围是1~6。这样就可以完成f(n - 1)到f(n) 的递推。
/**
* @param {number} n
* @return {number[]}
*/
var dicesProbability = function(n) {
let dp = Array(6).fill(1 / 6); // 初始化一个骰子的点数之和概率
for (let i = 2; i <= n; i++) { // 处理2-n个骰子的点数之和
let temp = Array(5 * i + 1).fill(0); // 初始化点数之和出现情况
for (let j = 0; j < dp.length; j++) { // 上一轮骰子的概率
for (let k = j; k < j + 6; k++) { // 本轮骰子的投掷情况
temp[k] += dp[j] / 6; // 重点，下面分析
}
}
dp = temp; // 赋值给dp，方便下一次循环
}
return dp;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
- 时间复杂度 O(n^2)。
- 空间复杂度 O(n)。
分析：
首先初始化f(1) 的结果。然后开始求f(2)，直到f(n) 。在外层循环内部，首先初始化n个骰子点数之和出现的可能性。然后在中层循环中根据上一轮概率来求解。
根据刚才得出的结论，f(n - 1, x) 仅与f(n, x + i) 相关，所以内层循环的起始值，与中层循环的j有关。而且k只需要累加6次。
内层循环里的表达式代表着：当添加本轮骰子时，骰子点数之和为k的值等于原有的值加上本轮投出1-6中某个点数的概率。而本轮投出1-6中某个点数的概率等于上一轮概率除以6。
每添加一个骰子，就将结果赋值给dp，方便进行下一轮骰子的点数之和判断。
最终返回dp数组即可。
# 总结
本题考查动态规划。难度系数困难。难点在于状态转移方程的推导以及实现成代码。
复杂度方面，中层循环的长度取决于上一轮循环的个数5n + 1 ，最终的时间复杂度是O(n^2) ，辅助数组的最大长度是5n - 4 ，因此空间复杂度是O(n) 。